package a_star

import (
	"errors"
	"fmt"
	"strings"
)

type tArrayHeap struct {
	comparator IComparator
	items []interface{}
	size int
	version int64
}

func newArrayHeap(comparator IComparator) IHeap {
	return &tArrayHeap{
		comparator: comparator,
		items: make([]interface{}, 0),
		size: 0,
		version: 0,
	}
}

func (me *tArrayHeap) Size() int {
	return me.size
}

func (me *tArrayHeap) IsEmpty() bool {
	return me.size <= 0
}

func (me *tArrayHeap) IsNotEmpty() bool {
	return !me.IsEmpty()
}

func (me *tArrayHeap) Push(value interface{}) {
	me.version++

	me.ensureSize(me.size + 1)
	me.items[me.size] = value
	me.size++

	me.ShiftUp(me.size - 1)
	me.version++
}


func (me *tArrayHeap) ensureSize(size int) {
	for ;len(me.items) < size; {
		me.items = append(me.items, nil)
	}
}

func (me *tArrayHeap) parentOf(i int) int {
	return (i - 1) / 2
}

func (me *tArrayHeap) leftChildOf(i int) int {
	return i*2 + 1
}

func (me *tArrayHeap) rightChildOf(i int) int {
	return me.leftChildOf(i) + 1
}

func (me *tArrayHeap) last() (i int, v interface{}) {
	if me.IsEmpty() {
		return -1, nil
	}

	i = me.size - 1
	v = me.items[i]
	return i,v
}

func (me *tArrayHeap) IndexOf(node interface{}) int {
	n := -1
	for i,it := range me.items {
		if it == node {
			n = i
			break
		}
	}

	return n
}

func (me *tArrayHeap) ShiftUp(i int) {
	if i <= 0 {
		return
	}
	v := me.items[i]

	pi := me.parentOf(i)
	pv := me.items[pi]

	if me.comparator.Less(v, pv) {
		me.items[pi], me.items[i] = v, pv
		me.ShiftUp(pi)
	}
}

func (me *tArrayHeap) Pop() (bool, interface{}) {
	if me.IsEmpty() {
		return false, nil
	}

	me.version++

	top := me.items[0]
	li, lv := me.last()
	me.items[0] = nil
	me.size--

	if me.IsEmpty() {
		return true, top
	}

	me.items[0] = lv
	me.items[li] = nil

	me.shiftDown(0)
	me.version++

	return true, top
}

func (me *tArrayHeap) shiftDown(i int) {
	pv := me.items[i]
	ok, ci, cv := me.minChildOf(i)
	if ok && me.comparator.Less(cv, pv) {
		me.items[i], me.items[ci] = cv, pv
		me.shiftDown(ci)
	}
}

func (me *tArrayHeap) minChildOf(p int) (ok bool, i int, v interface{}) {
	li := me.leftChildOf(p)
	if li >= me.size {
		return false, 0, nil
	}
	lv := me.items[li]

	ri := me.rightChildOf(p)
	if ri >= me.size {
		return true, li, lv
	}
	rv := me.items[ri]

	if me.comparator.Less(lv, rv) {
		return true, li, lv
	} else {
		return true, ri, rv
	}
}

func (me *tArrayHeap) String() string {
	level := 0
	lines := make([]string, 0)
	lines = append(lines, "")

	for {
		n := 1<<level
		min := n - 1
		max := n + min - 1
		if min >= me.size {
			break
		}

		line := make([]string, 0)
		for i := min;i <= max;i++ {
			if i >= me.size {
				break
			}
			line = append(line, fmt.Sprintf("%4d", me.items[i]))
		}
		lines = append(lines, strings.Join(line, ","))

		level++
	}

	return strings.Join(lines, "\n")
}

var gNoMoreElementsError = errors.New("no more elements")